'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 15:33:25
LastEditTime: 2025-09-08 15:47:09
'''



class Solution:

    def longestCommonSubsequence(self, text1, text2):

        M, N = len(text1), len(text2)

        dp = [[0] * (N + 1) for _ in range(M + 1)]

        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        
        return dp[-1][-1]
    

if __name__ == "__main__":
    
    text1 = "abcde"
    text2 = "ace"

    sol = Solution()
    res = sol.longestCommonSubsequence(text1, text2)
    print(res)


